package LeetCode._02算法基础.day04双指针;

import org.junit.Test;
import 题组.Solution;

import java.util.*;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 14 - 16:16
 * @Description 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，
 * 如果两者相等，返回 true 。# 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * @Version 简单
 */
public class _844比较含退格符的字符串 {
    static String s = "ab#c";   //ac
    static String t = "ad#c";   //ac
    @Test
    public void solve(){
        boolean res = backspaceCompare(s, t);
        System.out.println(res);
    }
    /*by me 倒序读取*/
    public boolean backspaceCompare(String s, String t) {
        return getPlainStr(s).equals(getPlainStr(t));
    }
    public String getPlainStr(String s){
        StringBuilder sb = new StringBuilder();
        //统计退格符
        int count = 0;
        //指针
        int p = s.length() - 1;
        while(p >= 0){
            if(s.charAt(p) == '#'){
                count++;
            }else{
                if(count == 0){
                    sb.append(s.charAt(p));
                }else{
                    count--;
                }
            }
            p--;
        }
        return sb.reverse().toString();
    }

    /*官方思路 双指针*/
    public boolean backspaceCompare1(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {    //指向了会出现的字符
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            //两个字符都存在
            if (i >= 0 && j >= 0) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                //如果有一个字符是存在的，则不相等
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}
